/**
 * @author VernHe
 * @date 2021年06月03日 16:49
 */
public class Solution_0124 {
    public static void main(String[] args) {
        System.out.println(new Solution_0124().maxPathSum(new TreeNode(0)));
    }
    int maxVal = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxVal;
    }

    private int dfs(TreeNode node) {
        // 递归基
        if (node == null) {
            return 0;
        }

        // 左子树和右子树
        int leftVal = dfs(node.left);
        int rightVal = dfs(node.right);

        // 局部最大值（当前节点作为根节点）
        int partVal = leftVal + node.val + rightVal;
        maxVal = Math.max(maxVal, partVal);

        // 对外提供的最大值（当前节点不是根节点时）
        int outVal = node.val + Math.max(leftVal, rightVal);

        // 如果是负数，就返回0，相当于不走这里
        return outVal < 0 ? 0 : outVal;
    }
}
